﻿namespace Leetcode.N1278;

public class Solution
{
    public int PalindromePartition(string s, int k)
    {
        var n = s.Length;
        var changes = new int[n, n];
        this.InitChanges(changes, n);
        this.ComputeChanges(s, changes);

        var f = new int[n, k];
        for (int i = 0; i < n; i++)
        {
            f[i, 0] = changes[0, i];

            for (int j = 1; j <= Math.Min(i, k - 1); j++)
            {
                var minChange = int.MaxValue;
                for (int m = j; m <= i; m++)
                {
                    minChange = Math.Min(minChange, f[m - 1, j - 1] + changes[m, i]);
                }
                f[i, j] = minChange;
            }
        }
        return f[n - 1, k - 1];
    }

    private void InitChanges(int[,] changes, int n)
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = i; j < n; j++)
            {
                changes[i, j] = -1;
            }
        }
    }
    private void ComputeChanges(string s, int[,] changes)
    {
        var n = s.Length;
        for (int i = 0; i < n; i++)
        {
            for (int j = i; j < n; j++)
            {
                this.GetChanges(s, i, j, changes);
            }
        }
    }

    private int GetChanges(string s, int from, int to, int[,] changes)
    {
        if (changes[from, to] == -1)
        {
            if (from == to)
            {
                changes[from, to] = 0;
            }
            else if (from + 1 == to)
            {
                changes[from, to] = s[from] == s[to] ? 0 : 1;
            }
            else
            {
                changes[from, to] = (s[from] == s[to] ? 0 : 1) + this.GetChanges(s, from + 1, to - 1, changes);
            }
        }

        return changes[from, to];
    }
}
